package com.yoshino.leetcode.improve40.seventh;

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;
        ListNode root = new ListNode();
        root.next = head;
        while (head != null) {
            len++;
            head = head.next;
        }
        len =len -  n;
        head = root;
        while (len-- > 0) {
            head = head.next;
        }
        head.next = head.next.next;
        return root.next;
    }

    public ListNode detectCycle(ListNode head) {
        /**
         * 快慢指针：s, f
         * 假定 s = k, f = 2k
         * 从head到入环点（不含）有a个结点
         * 在环内相遇时slow距离入环点有b个结点（包括入环点和相遇点），
         *   环内剩下c个结点，（b + c = T）。
         * k - a = iT + b
         * 2k - a = nT + b
         *
         * k = (n - i)T = (n - i - 1)T + b + c
         *
         * => a = (n - 2i - 1)T + c
         *
         * 即走 c + 1个结点会到 入环点
         */
        if (head == null || head.next == null) {
            return null;
        }
        ListNode s = head, f = head;
        // 防止空指针
        while (f != null && f.next != null) {
            f = f.next.next;
            s = s.next;
            if (f == s) {
                break;
            }
        }
        if (f != s) {
            // 非环
            return null;
        }
        f = head;
        while (f != s) {
            s = s.next;
            f = f.next;
        }
        return f;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 后续结点是重合的，只用找到这些重复结点的第一个相等即可
        // 移动到等价的起点，即一同出发，出现的第一个重复的即为所求
        int al = 0, bl = 0;
        ListNode cur = headA;
        while (cur != null) {
            al++;
            cur = cur.next;
        }
        cur = headB;
        while (cur != null) {
            bl++;
            cur = cur.next;
        }
        if (al > bl) {
            // a长
            for (int i = 0; i < al - bl; i++) {
                headA = headA.next;
            }
        } else {
            for (int i = 0; i < bl - al; i++) {
                headB = headB.next;
            }
        }
        while (headA != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }

}